package com.xy6.algo.sort;

import java.util.Arrays;

/**
 * 归并排序
 * <pre>
 * 时间复杂度：O(nlgn)，空间复杂度：O(n)
 * 
 * 将数组n拆分为两个长度相同的子数组a、b
 * 将a拆分为两个长度相同的子数组c、d
 * 将b拆分为两个长度相同的子数组e、f
 * 递归拆分，直至两个子数组x、y元素个数为1
 * 合并两个有序子数组x、y，得到有序数组e2
 * 合并两个有序子数组，得到有序数组f2
 * 继续合并子数组，直至合并为一个数组，数组元素已按从小到大排列。
 * 
 * 合并两个有序子数组x、y，得到有序数组e2：
 * 初始化空数组arr，作为合并后的数组，长度为x.length+y.length；
 * 初始化标识位k为0，标记在合并数组中，已处理的元素索引。初始化i、j为0；
 * 遍历x，当前索引为i；内层遍历y，当前索引为j；
 * 比较i元素与y元素大小，如果i元素小于y元素，k元素=i元素，k++，遍历y终止；否则，k元素=j元素，k++；
 * 在y遍历结束，比较j与y.length大小，如果j大于等于y.length，说明y中元素都已合并到arr中，遍历x终止；
 * 遍历x、y终止后，将x、y中未遍历的元素复制到arr末尾
 * 此时两个有序子数组已合并为一个有序子数组
 * </pre>
 * 
 * @author zhang
 * @since 2017-06-25
 */
public class SortCombine {

	public static void main(String[] args) {
		int[] arr = new int[] { 1, 3, 5, 2 };
		int[] result = sort(arr);
		System.out.println(Arrays.toString(result));
	}

	/**
	 * 拆分数组
	 * <p>将数组拆分为长度相同的两个数组，直至子数组长度为1，开始合并
	 * 
	 * @param arr
	 */
	public static int[] sort(int[] arr) {
		int size1 = arr.length / 2;
		int size2 = arr.length - size1;
		int[] arr1 = new int[size1];
		int[] arr2 = new int[size2];
		for (int i = 0; i < size1; i++) {
			arr1[i] = arr[i];
		}
		for (int i = size1; i < arr.length; i++) {
			arr2[i - size1] = arr[i];
		}
		int[] arrLeft;
		int[] arrRight;
		if (size1 > 1) {
			arrLeft = sort(arr1);
		} else {
			arrLeft = arr1;
		}
		if (size2 > 1) {
			arrRight = sort(arr2);
		} else {
			arrRight = arr2;
		}
		
		return merge(arrLeft, arrRight);
	}

	/**
	 * 合并两个有序的子数组
	 * 
	 * @param arr1
	 * @param arr2
	 */
	public static int[] merge(int[] arr1, int[] arr2) {
		int size1 = arr1.length;
		int size2 = arr2.length;
		int size = size1 + size2;
		int[] arr = new int[size];

		int i = 0;
		int j = 0;
		int k = 0;
		for (; i < size1; i++) {
			for (; j < size2; j++) {
				if (arr1[i] <= arr2[j]) {
					arr[k++] = arr1[i];
					break;
				} else {
					arr[k++] = arr2[j];
				}
			}
			if(j >= size2){
				break;
			}
		}
		for (; i < size1; i++) {
			arr[k++] = arr1[i];
		}
		for (; j < size2; j++) {
			arr[k++] = arr2[j];
		}

		return arr;
	}

}
